The need for scheduling agents optimally in contact centers arises in a broad range of industry areas. Examples include call centers providing inbound or outbound services, telephone operator centers, catalog sales centers, hospitals, police stations, airports, maintenance and installation operations, manufacturing, etc. Agents may be call center operators, technicians, workers, servers, nurses, etc. Contact centers may include any service center providing services to its customers through their agents. Many manufacturing operations may also fit into a contact center paradigm with similar needs and challenges in terms of worker or crew scheduling. Scheduling agents may be done a day at a time by specifying daily shift start time, shift length, time for the relief and lunch breaks, or to cover an entire week specifying, in addition to specifying daily shift schedules, work and non-work days. Contact centers use one or more interaction media to provide the desired services to their customers. Interaction media (also referred to as “contact types”) may include telephone calls, web chat, email, fax, etc. It may also include contacts using different languages such as English, Spanish, etc., and/or different services such as sales, technical help, etc. Customers choose their time and media of contact to interact with the contact center agents. The contact type used by a customer may require an agent with a special skill (e.g. language skills, writing proficiency). Moreover, agents may possess only some of the skills needed to serve customers using different contact types. Agents with the same skill set form a skill group (also referred to as “agent skill group”).
One of the critical tasks in contact center management is workforce scheduling. In such systems, workload changes during the course of an operating day, and from one day to another during a week. While understaffing will lower labor costs, it will result in poor service levels and longer waiting times for customers. Overstaffing, on the other hand, will improve service levels and lower waiting times, but will result in underutilized agents and higher labor costs. Hence, it is important for contact center managers to schedule their workforce in an optimal manner to minimize labor costs while meeting the projected agent and skills requirements. The present invention provides a method for formulating the workforce scheduling environment and requirements at a plurality of contact centers as a Mixed Integer Linear Programming (MILP) model, and a solution algorithm for developing optimal schedules for agents.
Traditionally, the task of developing work schedules to meet the forecasted agent and skill requirements is carried out manually. Manual scheduling when there is time varying workload and agent requirements, various daily shift and weekly tour scheduling rules, and multiple agent groups with different sets of skills and full-time/part-time work requirements is laborious and inefficient. Manpower scheduling in a typical contact center environment may involve an astronomical number of potential schedules, making manual evaluation of even a very small fraction of them to find an efficient schedule impractical.
In the past, a number attempts were made to develop more effective methods for workforce scheduling. Even though terms such as “optimal schedule”, “optimized schedule” or “local optimal” were used in their descriptions, none of the prior art agent scheduling methods states or verifies the necessary and sufficient conditions for optimality in scheduling agent. Like the manual scheduling method, the prior art agent scheduling methods use a set of rules of thumb to develop agent schedules. None of them presents any evidence of, or guarantee the optimality of the schedules that may be obtained using the rules of their methods.
In the field of mathematical optimization, there are proven necessary and sufficient conditions for a solution to an optimization problem to satisfy in order to be the optimal (absolutely the best) solution (Taha, 1987, pages 743-779). The method of the present invention first develops an MILP model for which these necessary and sufficient conditions are well stated, and then uses an algorithm that would generate an optimal solution satisfying these conditions.
U.S. Pat. No. 5,911,134 issued on Jun. 8, 1999 to Castonguay et al. describes a method for developing weekly tour schedules in call centers for agents with a single skill type. This method describes tour and shift construction rules to select tour and daily shift templates from the available ones, one day at a time, using measures such as “coverage”, and break scheduling rules to schedule daily breaks (U.S. Pat. No. 5,911,134, col. 18, lines 26-46, and FIG. 11). The method also includes post-processing steps to eliminate the redundant tours, level break times, and take employee preferences into consideration. No evidence to suggest that the schedules obtained using these rules will satisfy the necessary and sufficient conditions for optimality in a workforce scheduling problem is provided or known. As in the case of manual scheduling, the existence of an astronomical number of potential schedules, even in small call center scheduling environments, makes it very unlikely to locate the optimal schedule with the tour and shift construction rules used by this method.
U.S. Pat. No. 6,044,355 issued on Mar. 28, 2000 to Crockett et al. describes a simulation method for developing weekly tour schedules in a contact center environment involving multiple agent groups with a plurality of skill sets, and a plurality of contact types requiring different agent skills. The method uses a scheduler and an Automatic Call Distributor (ACD) simulator. However, no working details or description of the scheduler, and how it develops a schedule is included in the patent document. It was disclosed that the method uses a “scheduler program” (U.S. Pat. No. 6,044,355, col. 6, lines 18-36). No evidence to suggest that the schedules obtained using the scheduler program considered will satisfy the necessary and sufficient conditions for optimality in a workforce scheduling problem is provided or known.
U.S. Pat. No. 6,278,978 issued on Aug. 21, 2001 to Andre et al. describes a method that may be used to post-process an initial schedule available from another source outside of the method by applying a rule-based interchange procedure. The method is provided for scheduling agents with a single skill type. The method begins by acquiring an agent schedule developed by another method. The method then unschedules an agent from a shift in the schedule, evaluates the value of a “score” function for all other schedules that may assign this agent to a different shift, and selects a shift using the score function to improve the schedule. The method also considers rescheduling of breaks, again using the score function. Interchanging two or more activities to improve the quality of an initial solution to a problem is a well-known strategy in the field of Optimization and the related research literature. It is also well known in the field of Optimization that interchanging (rescheduling) one or more agents and shifts simultaneously doesn't guarantee the optimality of the solution developed and the satisfaction of the optimality conditions.
A primary object of the present invention is to overcome these limitations of the prior art agent scheduling methods. The present invention uses Mixed Integer Linear Programming approach (MILP) (Wolsey, 1998) to develop a mathematical model of a workforce scheduling environment. A number of researchers including Danzig (1954) proposed MILP models for workforce scheduling. Difficulties with the use of the prior art MILP models for workforce scheduling are well documented (Nanda and Browne, 1992, page 206, Holloran and Byrn, 1986, page 13). The MILP model proposed by Dantzig (1954), for example, enumerates all possible combinations of shift and tour parameters resulting in tens of trillions of decision variables, making it very inefficient and impossible to solve even in small contact center environments. To overcome these limitations of the prior art MILP agent scheduling models, the present invention formulates daily break, and days-off scheduling implicitly (i.e. not explicitly enumerating all possible combinations). Thus, the method of the present invention formulates a significantly smaller but equally powerful MILP model, and uses various extensions of it.
A further limitation of the prior art MILP models is that they only consider agent scheduling environments involving a single agent skill group. Recent technological developments in ACD's used in call centers to queue and assign calls to agents, and incorporation of other types of contact media such as email and fax, made contact center managers to realize that agents with different types of skills are needed to be scheduled to handle these contact types (e.g. a Spanish speaking agent to answer a caller speaking in Spanish, or agents with good writing skills to respond to emails). Thus, the agent scheduling task became more complex since the agent scheduling method used should take the time-varying demand for different agent skill types, and available agent groups with different skill sets (e.g. Spanish & English speaking sales, Chinese & English writing for technical help emails, and English only agent groups) into consideration in scheduling agents. It is another object of the present invention to disclose a method for formulating MILP models for scheduling environments involving a plurality of agent skill groups, and a plurality of contact types with time-varying workload for specific agent skills.
The present invention also discloses a solution algorithm that solves a number of sub-problems (or nodes) with the use of the standard Branch and Cut (B&C) algorithm for MILP problems. The solution method supplements the B&C algorithm by a Rounding Algorithm (RA algorithm) to locate the optimal solution of the MILP model of the invention. The optimality condition (both necessary and sufficient) for an MILP model is well documented in the field of Optimization; An all-integer solution that satisfies all of the constraints of an MILP with a minimization (maximization) type objective function, and has an objective value that is better than the best lower bound (upper bound) for any of the sub-problems in the B&C algorithm is a global (i.e. absolute) optimal solution to that MILP model (Wolsey, 1998). Once the optimality condition is satisfied by an all-integer solution found during the execution of this solution algorithm (either in the B&C algorithm or in the RA algorithm), an optimal agent schedule is reported using the information in the optimal solution of the MILP model found.
It is still another object of the present invention to provide a computer implemented optimal workforce scheduling method for contact centers that schedule their workforce to meet varying workload during the course of a day, and from one day to another during a week.